<?php
/**
 * 通过栈实现队列功能
 * 思路就是通过2个栈实现(一个入队栈，一个出队栈)：入队时一个栈添加入队元素，此时队头被压在栈底；当操作出队、获取队头时候，只要出队栈为空
 * 则把入队栈给一次性弹出到出队栈，此时队头就是栈顶。
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbQueueInterface;

class StackQueue implements XxbQueueInterface
{
    /**
     * 入队栈
     * @var ArrayStack
     */
    private $enqueueStack;
    /**
     * 出队栈
     * @var ArrayStack
     */
    private $dequeueStack;

    public function __construct($capacity = 10)
    {
        $this->enqueueStack = new ArrayStack($capacity);
        $this->dequeueStack = new ArrayStack($capacity);
    }

    /**
     * 入队
     * @param $ele
     */
    public function push($ele)
    {
        $this->enqueueStack->push($ele);
    }

    /**
     * 出队
     */
    public function pop()
    {
        if ($this->dequeueStack->isEmpty()) {
            $size = $this->enqueueStack->getSize();
            for ($i=0; $i<$size; $i++) {
                $this->dequeueStack->push($this->enqueueStack->pop());
            }
        }

        $this->dequeueStack->pop();
    }

    /**
     * 获取队头
     * @return mixed
     */
    public function top()
    {
        if ($this->dequeueStack->isEmpty()) {
            $size = $this->enqueueStack->getSize();
            for ($i=0; $i<$size; $i++) {
                $this->dequeueStack->push($this->enqueueStack->pop());
            }
        }

        return $this->dequeueStack->top();
    }

    /**
     * 获取队尾
     * @return mixed
     */
    public function bottom()
    {
        if ($this->dequeueStack->isEmpty()) {
            $size = $this->enqueueStack->getSize();
            for ($i=0; $i<$size; $i++) {
                $this->dequeueStack->push($this->enqueueStack->pop());
            }
        }
        if ($this->enqueueStack->isEmpty()) {
            return $this->dequeueStack->bottom();
        } else {
            return $this->enqueueStack->top();
        }
    }

    /**
     * 获取队列中有几个元素
     * @return int
     */
    public function getSize()
    {
        return $this->enqueueStack->getSize() + $this->dequeueStack->getSize();
    }

    /**
     * 判断队列是否为空
     * @return bool
     */
    public function isEmpty()
    {
        return $this->enqueueStack->isEmpty() && $this->dequeueStack->isEmpty();
    }
}
